#include<bits/stdc++.h>
#define int long long
#define mid (tr[p].l+tr[p].r)/2
using namespace std;
struct f{int l,r,ch[(1<<4)],add[4];}tr[100005*4];
void wei(int p){
	int op=0;
	for(int i=0;i<4;i++) if(tr[p].add[i]) op|=(1<<i);
	for(int i=0;i<(1<<4);i++) tr[p].ch[i]=0;
	if(tr[p].l==tr[p].r){
		tr[p].ch[op]=1;
		return;
	}
	for(int i=0;i<(1<<4);i++){tr[p].ch[i|op]+=tr[p*2].ch[i]+tr[p*2+1].ch[i];}
}
void jianshu(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	if(l==r){tr[p].ch[0]=1;return;}
	jianshu(p*2,l,mid),jianshu(p*2+1,mid+1,r);
	wei(p);
}
void xiugai(int p,int l,int r,int ks,int k){
	if(tr[p].l>=l&&tr[p].r<=r){tr[p].add[ks]+=k;wei(p);return;}
	if(l<=mid) xiugai(p*2,l,r,ks,k);
	if(r>mid) xiugai(p*2+1,l,r,ks,k);
	wei(p);
}
int a[100005][6];
signed main(){
	freopen("reporter.in","r",stdin);
	freopen("reporter.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	int ans=0,n,k;cin>>n>>k;
	jianshu(1,1,n);
	for(int i=1;i<=n;i++){
		int x;cin>>x;
		if(a[x][0]){
			for(int i=min(k,a[x][0]);i>=1;i--){
				xiugai(1,a[x][i+1]+1,a[x][i],i-1,-1);
				a[x][i+1]=a[x][i];
			}
		}
		a[x][0]++;a[x][1]=i;
		for(int i=1;i<=min(k,a[x][0]);i++){
			xiugai(1,a[x][i+1]+1,a[x][i],i-1,1);
		}
		ans+=tr[1].ch[(1<<k)-1];
	}
	cout<<ans;
	return 0;
}
